Comptage de chaînes

 Propriété Nombre de chaînes de longueur  \(k\) qui relient le sommet  \(i\) au sommet \(j\)

Soit  \(n\) et  \(k\) deux entiers naturels non nuls et  \(A\) la matrice d’adjacence d’un graphe  \(G\) d’ordre  \(n\) dont les sommets sont numérotés de  \(1\) à \(n\) , puis rangés dans l’ordre croissant de leurs numéros. Le coefficient de la  \(i\) -ème ligne et de la  \(j\) -ème colonne de la matrice  \(A^k\) donne le nombre de chaînes (ou de chemins) de longueur  \(k\) reliant le sommet  \(i\) au sommet \(j\) .

Exemple

\(\begin{smallmatrix} \ A= & A^{5} =\\ \\\left(\begin{smallmatrix}0 & 1 & 0&0 & 0 & 0&0 & 0 & 0\\1 & 0 & 0&1 & 1 & 1&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 1&0 & 0 & 0\\0 & 1 & 0&0 & 1 & 0&0 & 0 & 0\\0 & 1 & 0&1 & 0 & 0&1 & 1& 0\\0 & 1 & 1&0 & 0 & 0&0 & 0 & 1\\0 & 0 & 0&0 & 1 & 0&0 & 0 & 0\\0 & 0 & 0&0 & 1 & 0&0 & 0 & 1\\0 & 0 & 0&0 & 0 & 1&0 & 1 & 0\\\end{smallmatrix}\right) & \left(\begin{smallmatrix} 2 & 22 & 6&9 & 10 & 3&7 & 8 & 8\\22 & 24 & 3&\mathbf{32} & 46 & 36&10 & 18 & 11\\6 & 3 & 0&8 & 9 & 13&2 & 6 & 1\\ 9 & \mathbf{32} & 8&18 & 31 & 12&9 & 11 & 15\\10 & 46 & 9&31 & 24 & 19&21 & 28& 12\\3 & 36 & 13&12 & 19 & 4&9 & 10 & 19\\7 & 10 & 2&9 & 21 & 9&2 & 3 & 7\\8 & 18 & 6&11 & 28 & 10&3 & 4 & 14\\8 & 11 & 1&15 & 12 & 19&7 & 14 & 2\\\end{smallmatrix}\right)\\\\&\textrm{32 chaînes de 5 arêtes}\\& \textrm{relient les sommets 2 et 4.}\end{smallmatrix}\)

La démonstration se fait par récurrence sur \(k\) , à  \(n\) fixé.